package org.basis.algorithm.dp;

/**
 * 最小硬币数量问题
 *
 * @author Mr_wenpan@163.com 2022/03/17 22:01
 */
public class MinCoin {

    public static void main(String[] args) {

    }

    public static int min(int[] nums, int target) {


        return 0;
    }

    /**
     * 暴力破解法，每个硬币都可以选择要或者不要
     *
     * @param nums  硬币集合
     * @param index 当前来到的位置
     * @param rest  还是多少钱需要凑
     * @return int 数量
     * @author Mr_wenpan@163.com 2022/3/17 10:03 下午
     */
    public static int f(int[] nums, int index, int rest) {
        // 非法
        if (rest < 0) {
            return -1;
        }
        if (rest == 0) {
            return 0;
        }
        if (index == nums.length) {
            // 是否还需要0元钱需要搞定
            return -1;
        }

        // rest > 0并且也有硬币
        // 要当前位置的硬币
        int p1 = f(nums, index + 1, rest - nums[index]);
        // 不要当前位置的硬币
        int p2 = f(nums, index, rest);

        if (p1 == -1 && p2 == -1) {
            return -1;
        } else {
            // p1和p2至少有一个不等于-1
            if (p1 == -1) {
                return p2;
            }
            if (p2 == -1) {
                return p1 + 1;
            }
            return Math.min(p1 + 1, p2);
        }

    }

    public static int count(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        return h(nums, 0, 0, target);
    }

    public static int h(int[] nums, int index, int sum, int target) {
        // base case
        if (index == nums.length) {
            return sum == target ? 1 : 0;
        }
        // 对于每个位置我都可以选择要或者不要
        // 要当前位置的钱
        int h1 = h(nums, index + 1, sum + nums[index], target);
        // 不要当前位置的钱
        int h2 = h(nums, index + 1, sum, target);

        // 整合 要当前位置 和 不要当前位置 所能得到的方法种数
        return h1 + h2;
    }

    public static int count2(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int[][] dp = new int[nums.length + 1][target + 1];
        return h2(nums, 0, 0, target, dp);
    }

    public static int h2(int[] nums, int index, int sum, int target, int[][] dp) {
        // 保证dp数组不越界
        if (sum > target) {
            return 0;
        }
        // 缓存
        if (dp[index][sum] != -1) {
            return dp[index][sum];
        }
        // base case
        if (index == nums.length) {
            return dp[index][sum] = sum == target ? 1 : 0;
        }
        // 对于每个位置我都可以选择要或者不要
        // 要当前位置的钱
        int h1 = h(nums, index + 1, sum + nums[index], target);
        // 不要当前位置的钱
        int h2 = h(nums, index + 1, sum, target);

        // 整合 要当前位置 和 不要当前位置 所能得到的方法种数
        return dp[index][sum] = h1 + h2;
    }
}
